#ifndef SYSYF_COMSUBEXPRELI_H
#define SYSYF_COMSUBEXPRELI_H

#include "Pass.h"
#include <map>
#include <unordered_map>
#include <set>
#include "Instruction.h"

class myset
{
public:
    myset()
    {
        __size = 0;
        __set.clear();
    }
    myset(int size, bool fill = false)
    {
        __size = size;
        __set.clear();
        if (size == 0) return;
        if (fill)
        {
            while (size > 32)
            {
                __set.push_back(-1);
                size -= 32;
            }
            __set.push_back(((1 << size - 1) - 1 << 1) | 1);
        }
        else
        {
            while (size > 0)
            {
                __set.push_back(0);
                size -= 32;
            }
        }
    }
    myset(const myset& a)
    {
        __size = a.__size;
        __set = a.__set;
    }
    void print()
    {
        for (int i = __set.size() - 1; i >= 0; i--)
            printf("%x ",__set[i]);
        printf("\n");
    }
    void join(int x);
    bool exist(int x);
    friend myset operator & (myset& a, myset& b);
    friend myset operator | (myset& a, myset& b);
    friend bool operator == (myset& a, myset& b);
private:
    int __size;
    std::vector<uint32_t> __set;
};

struct exprinst
{
    Value* left, * right;
    Instruction::OpID id;
};

bool operator < (exprinst a, exprinst b);
bool operator == (exprinst a, exprinst b);

/*****************************CommonSubExprElimination**************************************/
/***************************This class is based on SSA form*********************************/
/***************************you need to finish this class***********************************/
class ComSubExprEli : public Pass 
{
public:
    explicit ComSubExprEli(Module* module):Pass(module){}
    const std::string get_name() const override {return name;}
    void execute() override;
    static bool is_valid_expr(Instruction* inst);

    void delete_in_blocks();
    void create_inst_list();
    void create_e_gen();
    void calc_in_out();
    void delete_global();
private:
    const std::string name = "ComSubExprEli";
    Function* func_;
    std::vector<exprinst> inst_list;
    std::map<BasicBlock*, myset> e_gen;
    std::map<BasicBlock*, myset> IN;
    std::map<BasicBlock*, myset> OUT;
};

#endif // SYSYF_COMSUBEXPRELI_H